//
// Created by dengspc on 2019/2/13.
//

#ifndef INC_010_ALGORITHM_BAG_H
#define INC_010_ALGORITHM_BAG_H
#include <ostream>
#include <vector>

using namespace std;

template <typename Type>
class Bag{
private:
    struct Node{
        Type type;
        Node * next;

        Node(Type type, Node* next = NULL){
            this->type = type;
            this->next = next;
        }
    };

    Node* first;

    void _destory(Node* node){
        if(node == NULL)
            return ;
        _destory(node->next);
        delete node;
    }
public:
    Bag(){
        first = NULL;
    }

    ~Bag(){
        _destory(first);
    }
    void add(Type type){
        Node* nNode = new Node(type);
        if(first == NULL) {
            first = nNode;
            return ;
        }
        Node* last = first;
        Node* pre = NULL;
        while(last != NULL){
            pre = last;
            last = last->next;
        }
        pre->next = nNode;
    }

    int size(){
        int size = 0;
        Node* last = first;
        while(last != NULL){
            last = last->next;
            size ++;
        }
        return size;
    }

    bool isEmpty(){
        return first == NULL;
    }

    vector<Type>* getVector(){
        vector<Type>* vector1 = new vector<Type>();
        Node* last = first;
        while(last != NULL){
            vector1->push_back(last->type);
            last = last->next;
        }
        return vector1;
    }

};
#endif //INC_010_ALGORITHM_BAG_H
